CS-04 : DATA STRUCTURE THROUGH
'C' & PASCAL JUNE 1997
| Time : 2 Hours |
Max. Marks : 60 |
NOTE : Question 1 is compulsory. Attempt any three from the
rest. Algorithms should be written near to C or Pascal language statements.
1. (i) Write a complete program in
C-language to reverse the characters in a string from starting position to end
position recursively. The program must have a function rev-strg (string, start,
end).
(ii) Construct a binary tree whose nodes are, in two orders as under:
Inorder traversal : B, C, E, D, F. A. G, H
Postorder traversal : A, B, C, D, E, F, G, H
(iii) (a) Show through appropriate data structure the representation of the
following 4 X 4 sparse matrix:
0 0 11 0
12 0 0 0
0 -4 0 0
0 0 0 -25
(b) Write an algorithm to
create the matrix C = A + B where A & B are two sparse matrices. Your
algorithm should leave the matrices unchanged and setup new matrix in accordance
with this data representation.
(iv) Write the prefix form of the following expression: (Assuming C- language
expression)
!| a & & ! (b < c ) || ( c < e)
a & & b || c || ! (e > f)
2. (i) Write an algorithm to
generate fully parenthesized infix expression from their prefix form.
(ii) Write an algorithm to evaluate a prefix expression.
3. (i) Draw the internal memory
representation of the following binary tree using
sequential
Linked
(ii) Write a non-recursive version of function postorder.
4. (i) For the graph given below:
Draw
(a) Its adjacency list representation.
(b) Its adjacency multilist representation.
(ii) Write a non-recursive version of quick-sort algorithm.
6. A double ended queue (dequeue) is a linear list in which addition and deletion can be made at either end. Discuss data structure mapping of a dequeue into one dimentional array. Write algorithm to add and delete elements from either end of the dequeue.